// m

// 给定一个整数数组postorder，数组的任意两个数字都互不相同
// 要求，判断该数组是不是某二叉搜索树的后序遍历结果，如果是，返回true，否则返回false

// 解题思路：
// 后序遍历的顺序为：左-右-根，而二叉搜索树的定义是：左子树所有节点值<根节点，右子树所有节点值 > 根节点值
// 所以可以把数组最右侧元素作为二叉搜索树的根节点值，然后判断数组的左右两侧是否符合左侧都小于该节点值，右侧值都大于该节点值，如果不满足，则说明不是某二叉搜索树的后序遍历结果
// 找到左右分界线位置，然后递归左右数组继续查找
// 终止条件为数组开始位置 > 结束位置，此时该树的子节点数目小于等于1，直接返回true即可

function verifyPostorder(postorder) {
    function verify(left, right) {
        if (left >= right) {
            return true
        }
        let index = left
        while (postorder[index] < postorder[right]) {
            index += 1
        }
        let mid = index
        while (postorder[index] > postorder[right]) {
            index += 1
        }
        return index === right && verify(left, mid - 1) && verify(mid, right - 1)
    }
    if (postorder.length <= 2) {
        return true
    }
    return verify(0, postorder.length - 1)
}

let postorder = [1,3,2,6,5]
console.log(verifyPostorder(postorder))